package Hot100.Medium.GreedyAndDP.DynamicPlanning;

public class LC152_MaxProductOfSubArray {
    public static void main(String[] args) {

    }
    public int maxProduct(int[] nums){
        if(nums.length == 0){
            return 0;
        }
        int ans = nums[0];
        // 定义两个DP，最大dp数组以及最小dp数组，因为最小值可能为负数，但没准下一步乘以一个负数，当前的最大值就变成最小值，而最小值则变成最大值了
        // maxDP[i]表示数组中前i个数相乘得到的最大积；
        int[] maxDP = new int[nums.length];
        int[] minDP = new int[nums.length];
        // 初始化DP数组
        // 对于maxDP，以及minDP，因为还没相乘，因此都先赋值为数组中的第一个数
        maxDP[0] = nums[0];
        minDP[0] = nums[0];
        // 确定递推公式，对于maxDP[i]，可以上一个最大积与当前第i个元素相乘，或者上一个最小积与当前元素相乘（原因刚开始说过，因为负负得正），对于minDP[i]同理
        // 与自己比较是为了防止之前的数都为0
        for(int i = 1; i < nums.length; i++){
            maxDP[i] = Math.max(nums[i], Math.max(maxDP[i - 1] * nums[i], minDP[i - 1] * nums[i]));
            minDP[i] = Math.min(nums[i], Math.min(maxDP[i - 1] * nums[i], minDP[i - 1] * nums[i]));
            ans = Math.max(ans, maxDP[i]);
        }
        return ans;
    }
}
